import java.io.Console;
import java.util.Random;

class Solution382 {


    private ListNode head;
    private int length;
    private Random random;

    /**
     * @param head The linked list's head.
     *             Note that the head is guaranteed to be not null, so it contains at least one node.
     */
    public Solution382(ListNode head) {
        this.head = head;
        for (ListNode node = head; node != null; node = node.next) {
            this.length++;
        }
        this.random = new Random();
    }

    /**
     * Returns a random node's value.
     */
    public int getRandom() {
        ListNode result = head;
        int n = random.nextInt(length);
        for (int i = 0; i < n; i++) {
            result = result.next;
        }
        return result.val;
    }
}